package com.dyz.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class FindAnagrams438 {
    public static void main(String[] args) {
        List<Integer> anagrams = new FindAnagrams438().findAnagrams("cbaebabacd", "abc");
        System.out.println(anagrams);
    }
    public List<Integer> findAnagrams(String s, String p) {
        //SD框架
        //1。 把右指针右移
        //2. 右移左指针，直到条件不符合
        //3. 重复 1， 2步骤
       int start =0, left=0,right=0;
       int match=0;
       List<Integer> res = new ArrayList<>();
        HashMap<Character, Integer> window = new HashMap<>();
        HashMap<Character, Integer> needs = new HashMap<>();
        for(char c: p.toCharArray()){
            needs.put(c, needs.getOrDefault(c, 0)+1);
        }

        while (right<s.length()){
            //右指针移动
            char c1 = s.charAt(right);
            if(needs.containsKey(c1)){
                window.put(c1, window.getOrDefault(c1,0)+1);
                if(window.get(c1).equals(needs.get(c1))){
                    match++;
                }
            }
            else
            {
                left = right +1;
                window = new HashMap<>();
                match =0;
            }
            right++;

            //左指针移动
            while (match==needs.size()){
                start = left;
                if(window.equals(needs)){
                    res.add(start);
                }
                char c2 = s.charAt(left);
                if (window.containsKey(c2)) {

                    window.put(c2, window.get(c2)-1);
                    if(window.get(c2)<needs.get(c2)){
                        match--;
                    }
                }
                left++;
            }
        }
       return res;
    }
}
